#pragma once

namespace solution_069
{

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0 || x == 1)
            return x;
        int i = 1;
        int j = 2;
        while (true) {
            if (j <= x / j) {
                i = j;
                j *= 2;
            } else {
                break;
            }
        }
        while (true)
            if ((i + 1) <= x / (i + 1))
                ++i;
            else
                return i;
    }
};

}  /* namespace solution_069 */
